package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/">删除排序链表中的重复元素 II(Remove Duplicates from Sorted List II)</a>
 * <p>给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,3,4,4,5]
 *      输出：[1,2,5]
 *
 * 示例 2：
 *      输入：head = [1,1,1,2,3]
 *      输出：[2,3]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *      <li>链表中节点数目在范围 [0, 300] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *      <li>题目数据保证链表已经按升序 排列</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0082RemoveDuplicatesFromSortedList_II_M 删除排序链表中的重复元素 II(Remove Duplicates from Sorted List II)
 * @see LC0083RemoveDuplicatesFromSortedList_S 删除排序链表中的重复元素(Remove Duplicates from Sorted List)
 * @since 2023/4/27 11:06
 */
public class LC0082RemoveDuplicatesFromSortedList_II_M {

    static class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            // 如果链表中无节点或者只有一个节点，直接返回
            if (head == null || head.next == head) {
                return head;
            }
            // 给链表加一个虚拟节点，避免链表头被删除
            ListNode dummyHead = new ListNode(-1, head);
            ListNode currNode = dummyHead;
            while (currNode.next != null && currNode.next.next != null) {
                if (currNode.next.val != currNode.next.next.val) {
                    currNode = currNode.next;
                } else {
                    int val = currNode.next.val;
                    while (currNode.next != null && currNode.next.val == val) {
                        currNode.next = currNode.next.next;
                    }
                }
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(3);
        head2.next.next.next.next = new ListNode(4);
        head2.next.next.next.next.next = new ListNode(4);
        head2.next.next.next.next.next.next = new ListNode(5);
        Solution solution = new Solution();
        Printer.printListNode(solution.deleteDuplicates(head));
        Printer.printListNode(solution.deleteDuplicates(head2));
    }
}
